import java.util.Arrays;

// https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150
public class q1 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        method1(nums1, m, nums2, n);
        method2(nums1, m, nums2, n);
    }

    /**
     * 简单sort
     * 1ms
     * 复杂度O(nlogn)
     */
    public void method1(int[] nums1, int m, int[] nums2, int n) {
        if (n >= 0) {
            System.arraycopy(nums2, 0, nums1, m, n);
        }
        Arrays.sort(nums1);
    }

    /**
     * 逆序双指针 -> 避免元素被覆盖
     * 0ms
     * 复杂度O(n+m)
     */
    public void method2(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        // 从后往前比较大小，大的覆盖0
        while (i >= 0 && j >= 0) {
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
        // 若j有剩余，则全部放在nums1前部分
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        new q1().merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1));
    }
}
